package b_sorting_advance.b_quick_sort;

import com.sun.javafx.collections.SortHelper;
import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingHelper;
import utils.sorting_helper.SortingTest;

import java.util.Random;

/**
 * @Author: DeLucia
 * @Description: 快速排序号称20世界最重要的算法之一
 * @Date: 2019/1/24 0:48.
 */
@SuppressWarnings("unchecked")
public class QuickSorting2Ways extends SortingTest {

    @Override
    public void sort(ArrayGeneric arr) {
        quickSort2ways(arr, 0, arr.length() - 1);
    }

    /**
     * 问题
     * 1. 没有对小规模数组使用插入排序提高性能
     * 2. 基准选取过大和过小时影响效率， 尤其对有序数组排序效率最差， 将退化成N2时间复杂度
     * 3. 递归层次过深容易出现栈溢出
     * 4. 当重复元素多的时候极容易造成左右两边严重不对等, 效率大大降低
     * 优化
     * 1. 当递归规模小于16的时候直接使用插入排序提高性能
     * 2. 在数组中随机选取一个元素作为基准 - 可以保证在数据量足够大的时候 概率上趋近NlogN时间复杂度
     * 3. 从左右两侧双路扫描 直到在中间收拢 - 可以保证值和基准相等的元素均匀分配在左右两侧
     *
     * @param arr
     * @param l
     * @param r
     */
    private void quickSort2ways(ArrayGeneric arr, int l, int r) {
        // 优化点1： 当递归规模小于16的时候直接使用插入排序提高性能
        //if (l >= r) // 递归的终点
        //    return;
        if (r - l <= 15) {
            insertionSort(arr, l, r);
            return;
        }
        // 优化点2: 采用两路分区法
        int p = partition2Ways(arr, l, r);
        quickSort2ways(arr, l, p - 1);
        quickSort2ways(arr, p + 1, r);
    }

    /**
     * 分区操作 - 快速排序的核心
     * 第二个版本：选取随机元素作为基准 从左右两侧双路扫描 直到在中间收拢
     * <p>
     * 原来的单路固定基准的方式存在的问题：
     * <p>
     * 1. 最差情况即当数组完全有序的时候，将退化成O(N^2)的时间复杂度,因为基准每次都是被放置在一侧
     * 2. 当存在重复元素的时候重复元素会集中在左侧导致基准严重偏斜,大大降低效率
     * <p>
     * 针对以上问题做的优化：
     * 1. 在数组中随机选取一个元素作为基准 - 可以保证在数据量足够大的时候 概率上趋近NlogN时间复杂度
     * 2. 从左右两侧双路扫描 直到在中间收拢 - 可以保证值和基准相等的元素均匀分配在左右两侧
     * <p>
     * 仍存在的问题:
     * 两路固然性能有了一定提升, 但是重复元素的操作还是会造成性能损耗
     * (接下来介绍的三路排排序将不对重复元素进行处理, 大大提升对重复元素多的数据的排序性能)
     *
     * @param arr 分区的数据
     * @param l   分区操作的左坐标
     * @param r   分区操作的有坐标
     * @return 分区后基准所在下标
     */
    private int partition2Ways(ArrayGeneric arr, int l, int r) {

        // 优化 选取随机元素作为基准
        arr.swap(l, (int)(Math.random()*(r - l + 1) + l)); // l0r4 range 0-4 5

        Comparable ref = arr.get(l); // 默认将l所在元素当做参考值进行分区

        // i是从左侧进行扫描的下标 从 l+1开始++  扫描期间保证 arr[l+1..i-1] >= ref
        // j是从右侧进行扫描的下标 从r开始--     扫描期间保证 arr[j+1..r] >= ref
        // 扫描结束时 i = j
        int i = l + 1, j = r;


        // 两路向中间收缩
        while (true) {

            // i从左侧l+1开始向右扫描, 没有越界并且小于ref的时候继续向右扫描, 直到越界或者碰到大于等于ref的元素时停止扫描
            while (i <= r && arr.get(i).compareTo(ref) < 0) i++;
            // j从右侧r开始向左扫描, 没有越界并且大于ref的时候继续向左扫描, 直到越界或者碰到小于等于ref的元素时停止扫描
            while (j >= l && arr.get(j).compareTo(ref) > 0) j--;

            // 结束条件
            if (i > j) break;

            // 将i所在的大于等于ref的元素 和 j所在的小于等于ref的元素交换
            // 交换后可以保证 左边新元素小于等于ref 右边新元素大于等于ref
            arr.swap(i, j);
            i++;
            j--;
        }

        // 最后将l所在的基准放到j处 使j的左边小于等于ref,j的右边大于等于ref
        arr.swap(l, j);

        return j;
    }

    /**
     * 当递归到数组规模小于16的时候
     * 为了提高性能改用插入排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private void insertionSort(ArrayGeneric arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            Comparable e = arr.get(i);
            int j;
            for (j = i; j > left && arr.get(j - 1).compareTo(e) > 0; j--) {
                arr.put(j, arr.get(j - 1));
            }
            arr.put(j, e);
        }
    }

    @Test
    public void testingquickSort2ways() {
        ArrayGeneric<Integer> arr = getRandomIntegerArray(26, 0, 9);
        System.out.println(arr);
        quickSort2ways(arr, 0, arr.length() - 1);
        System.out.println(arr);
    }

    @Test
    public void testingSortMethod() {
        ArrayGeneric<Integer> arr = getRandomIntegerArray(2000000, 0, 9);
//        System.out.println(arr);
        long begin = System.currentTimeMillis();
        sort(arr);
        long end = System.currentTimeMillis();
//        System.out.println(arr);
        assert SortingHelper.testSorted(arr);
        System.out.println((end-begin) + "ms");
    }

    @Test
    public void testDeepClone() throws CloneNotSupportedException {
        ArrayGeneric arr = getRandomIntegerArray(20, 0, 9);
        ArrayGeneric arr2 = arr.clone();
        sort(arr);
        System.out.println(arr);
        System.out.println(arr2);
    }

}
